home *** CD-ROM | disk | FTP | other *** search
/ Skunkware 5 / Skunkware 5.iso / lib / calc / psqrt.cal < prev    next >
Text File  |  1995-07-17  |  1KB  |  57 lines
  1. /*
  2.  * Copyright (c) 1993 David I. Bell
  3.  * Permission is granted to use, distribute, or modify this source,
  4.  * provided that this copyright notice remains intact.
  5.  *
  6.  * Calculate square roots modulo a prime.
  7.  *
  8.  * Returns null if number is not prime or if there is no square root.
  9.  * The smaller square root is always returned.
  10.  */
  11.  
  12. define psqrt(u, p)
  13. {
  14.     local    p1, q, n, y, r, v, w, t, k;
  15.  
  16.     p1 = p - 1;
  17.     r = lowbit(p1);
  18.     q = p >> r;
  19.     t = 1 << (r - 1);
  20.     for (n = 2; ; n++) {
  21.         if (ptest(n, 1) == 0)
  22.             continue;
  23.         y = pmod(n, q, p);
  24.         k = pmod(y, t, p);
  25.         if (k == 1)
  26.             continue;
  27.         if (k != p1)
  28.             return;
  29.         break;
  30.     }
  31.     t = pmod(u, (q - 1) / 2, p);
  32.     v = (t * u) % p;
  33.     w = (t^2 * u) % p;
  34.     while (w != 1) {
  35.         k = 0;
  36.         t = w;
  37.         do {
  38.             k++;
  39.             t = t^2 % p;
  40.         } while (t != 1);
  41.         if (k == r)
  42.             return;
  43.         t = pmod(y, 1 << (r - k - 1), p);
  44.         y = t^2 % p;
  45.         v = (v * t) % p;
  46.         w = (w * y) % p;
  47.         r = k;
  48.     }
  49.     return min(v, p - v);
  50. }
  51.  
  52.  
  53. global lib_debug;
  54. if (lib_debug >= 0) {
  55.     print "psqrt(u, p) defined";
  56. }
  57.